function [ minGraph ] = CompInitialMinGraph( fullGraphV,userFtPt,fullGraphVDistanceMtr,userFtPtDistanceMtr )

% ftPts: list of feature points of increasing entropy

nbFtPt=numel(fullGraphV);
compCost=zeros(nbFtPt,1);
for i=1:nbFtPt
    compCost(i)=fullGraphVDistanceMtr(i,userFtPt);
end

[~,sortedFtPts]=sort(compCost);

% Add the feature points until the matching is correct
ftPtIdx=1;
minGraph=sortedFtPts(ftPtIdx);
[OK, maxDist] = QualityOfGraph(userFtPt,minGraph,fullGraphVDistanceMtr,userFtPtDistanceMtr);
while OK==false && ftPtIdx<numel(sortedFtPts)
    ftPtIdx=ftPtIdx+1;
    newMinGraph=[minGraph,sortedFtPts(ftPtIdx)];
    [OK, newMaxDist] = QualityOfGraph(userFtPt,newMinGraph,fullGraphVDistanceMtr,userFtPtDistanceMtr);
    if newMaxDist<maxDist
        minGraph=newMinGraph;
        maxDist=newMaxDist;
    end
end

        
% Add more feature points to minGraph if minGraph is too small
ftPtIdx=1;
while numel(minGraph)<6     % 6 vertices at least
    if numel(find(minGraph==sortedFtPts(ftPtIdx),1,'first'))==0
        minGraph=[minGraph,sortedFtPts(ftPtIdx)];
    end
    ftPtIdx=ftPtIdx+1;
    if ftPtIdx>numel(sortedFtPts)
        break;
    end
end

% Add more feature points 
global maxGeoDist;
neighbVertFlag=userFtPtDistanceMtr<(maxGeoDist*0.6);    % 0.6 for the cat
neighbVertIdx=find(neighbVertFlag==1);
% Find vertices whose geodesic distance to ftPt becomes all larger
while true
    notWellDefinedV=[];
    for i=1:numel(neighbVertIdx)
        if ~any(fullGraphVDistanceMtr(minGraph,neighbVertIdx(i))<fullGraphVDistanceMtr(minGraph,userFtPt))
            notWellDefinedV=[notWellDefinedV,neighbVertIdx(i)];
        end
    end
    % Stop condition
    if numel(notWellDefinedV)==1
        assert(notWellDefinedV==userFtPt);
        break
    end
    % Find the closest feature point
    remainingFtPts=setdiff(1:numel(fullGraphV),minGraph);    % Get remaining feature points
    minFtPt=realmax;
    minFtPtIdx=0;
    for i=1:numel(remainingFtPts)
        [minVal,~]=min(fullGraphVDistanceMtr(remainingFtPts(i),neighbVertIdx));     % Find the closest ftPt
        if minVal<minFtPt
            minFtPt=minVal;
            minFtPtIdx=remainingFtPts(i);
        end
    end
    minGraph=[minGraph,minFtPtIdx];
    if numel(minGraph)==numel(fullGraphV)
        break;
    end
end

minGraph=fullGraphV(minGraph);
end


function [OK, maxDist] = QualityOfGraph(userFtPt,minGraph,fullGraphVDistanceMtr,userFtPtDistanceMtr)
global edgeDelta;
% Compute the number of vertices of equal geodesic distance to the ftPtGraph
nbV=size(fullGraphVDistanceMtr,2);
foundV=true(nbV,1);
for i=1:numel(minGraph)
    dist=fullGraphVDistanceMtr(minGraph(i),userFtPt);
    for j=1:nbV
        if foundV(j)==false
            continue;
        end
        if abs(dist-fullGraphVDistanceMtr(minGraph(i),j))>edgeDelta
            foundV(j)=false;
        end
    end
end

% Compute the largest geodesic distance from the matching vert to the userFtPt
maxDist=max(userFtPtDistanceMtr(foundV));
 
OK=(maxDist<edgeDelta*2);

end


